package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         774,
		Discription: "在一些加油站中添加k个加油站，使得相邻两个加油站的最大距离最小",
		Level:       3,
		Labels: map[string]int{
			"二分查找":  1,
			"小数二分": 1,
			"单调函数二分": 1,
		},
	})
}

func MinmaxGasDist(stations []int, k int) float64 {
	if len(stations) <= 1 {
		return 0.0
	}

	satisfyMinDistance := func(distance float64) bool {
		count := 0
		for i := 1; i < len(stations); i++ {
			count += int((float64(stations[i]-stations[i-1]) - 1e-7) / distance)
		}

		return count <= k
	}

	maxDistance := stations[1] - stations[0]
	for i := 2; i < len(stations); i++ {
		maxDistance = max(maxDistance, stations[i]-stations[i-1])
	}

	left := float64(0)
	right := float64(maxDistance)
	for right-left >= 1e-6 {
		mid := left + (right-left)/2.0
		if satisfyMinDistance(mid) {
			right = mid
		} else {
			left = mid
		}
	}

	return left
}